#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        vector<vector<int>> ans;
        int size = nums.size();
        if (size < 3)
        {
            return ans;
        }
        int index1, index2, index3 = size, value1, value2, value3;
        sort(nums.begin(), nums.end());
        for (index1 = 0; index1 < size - 2; index1++)
        {
            index2 = index1 + 1;
            index3 = size - 1;
            if (index1 > 0 && nums[index1] == value1)
            {
                continue;
            }
            value1 = nums[index1];
            while (index2 < index3 && index2 < size && index3 >= 0)
            {
                value2 = nums[index2];
                value3 = nums[index3];
                if (value1 + value2 + value3 == 0)
                {
                    ans.push_back({value1, value2, value3};);
                    while (index2 + 1 < size && nums[index2] == nums[++index2])
                        ;
                }
                else if (value1 + value2 + value3 > 0)
                {
                    while (index3 - 1 >= 0 && nums[index3] == nums[--index3])
                        ;
                }
                else
                {
                    while (index2 + 1 < size && nums[index2] == nums[++index2])
                        ;
                }
            }
        }

        return ans;
    }
};
int main(int argc, char const *argv[])
{
    /* code */
    Solution s;
    vector<int> nums = {1, -1, -1, 0};
    vector<vector<int>> result = s.threeSum(nums);
    cout << "[";
    for (int i = 0; i < result.size(); i++)
    {
        cout << "[";

        for (int j = 0; j < result[i].size(); j++)
        {
            cout << result[i][j] << ",";
        }
        cout << "]";
    }
    cout << "]";

    return 0;
}
